import java.util.LinkedList;
import java.util.Queue;

public class Tree {

    // Encodes a tree to a single string.
    public static String serialize(TreeNode root) {
        if(root==null){
            return "#!";
        }
        String ans = root.val+"!";
        ans += serialize(root.left);
        ans += serialize(root.right);
        return ans;
    }

    // 根据字符串建树
    public static TreeNode deserialize(String data) {
        String[] array = data.split("!");
        Queue<String> queue = new LinkedList<>();
        for(int i=0;i<array.length;i++){
            queue.add(array[i]);
        }
        return preorder(queue);
    }


    public static TreeNode preorder(Queue<String> queue){
        String value = queue.poll();
        if(value.equals("#")){
            return null;
        }
        TreeNode head = new TreeNode(Integer.valueOf(value));
        head.left = preorder(queue);
        head.right = preorder(queue);
        return head;
    }

    public static void main(String[] args) {
        String str = "1!2!3!";
        /*for (String t : str.split("!")) {
            System.out.println(t);
        }*/

        TreeNode root = deserialize(str);
       // String s = serialize(root);
        //System.out.println(s);

    }


}

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
